package com.captain.special.链表;

import com.captain.leetcode.链表.ListNode;

import java.util.List;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/3/27 11:04
 */
public class 对链表进行插入排序147 {
    public static void main(String[] args) {
        new 对链表进行插入排序147().insertionSortList(ListNode.getInstance());

    }

    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1,head);
        ListNode last = head;
        //从第二个开始排序
        ListNode cur = head.next;
        //42135
        while (cur != null) {
            //两种情况,一种最后排序的值比当前值小或者相等
            if (last.val <= cur.val) {
                last = last.next;
            } else {
                //最后的值大于当前值
                ListNode pre = dummy;
                //-1 5 4 321
                //从前向后进行比较,如果比它小,则继续往后移动
                while (pre.next.val <= cur.val) {
                    pre = pre.next;
                }
                //找到插入元素的位置,进行链表的操作
                last.next = cur.next;
                cur.next = pre.next;
                pre.next = cur;
            }
            cur = last.next;
        }
        return dummy.next;
    }
}
